package graph

import (
//    "fmt"
)

// Parallel BFS
// Returns the BFS tree of the original
func (g *EdgeMap) ParallelBFS(start VertexID) *EdgeMap {
    bfs_tree := CreateEdgeMap(g.Order())
    //numVertices := g.Order()
    numEdges := g.edgeCount
    // Keep track of vertices visited
    visited := make(map[VertexID]bool)
    frontier := make([]VertexID, numEdges)

    frontier[0] = start
    bottom, top := 0, 1
    visited[start] = true
    bfs_tree.AddVertex(start)

    for top > bottom {
        // Pop next vertex from frontier
        currentVertex := frontier[bottom]
        bottom++
        neighbors := g.NeighborsIterator(currentVertex)

        for nV, valid := <-neighbors; valid; nV, valid = <-neighbors {
            if visited[nV] == false {
                frontier[top] = nV
                top++
                bfs_tree.AddVertex(nV)
                bfs_tree.AddEdge(currentVertex, nV)
                visited[nV] = true
            }
        }
    }
    return bfs_tree
}
